#include <stdio.h>
#include <stdlib.h>
#include "bst.h"

static BOOL findHelp(struct Bst *_pbst, struct Node *_subroot, void *data)
{
	if(_subroot==NULL)
		return false;

	if(_pbst->dataCmp(data, _subroot->data)==1)
		return findHelp(_pbst, _subroot->right, data);
	else if(_pbst->dataCmp(data, _subroot->data)==-1)
		return findHelp(_pbst, _subroot->left, data);
	else
		return true;
}

static BOOL removeHelp(struct Bst *_pbst, 
					   struct Node *ppNode, 
					   int pivot, 
					   struct Node *_subroot, 
					   void *data)
{
	if(_subroot==NULL)
		return false;
	else
	{
		if(_pbst->dataCmp(data, _subroot->data)==1)
			return removeHelp(_pbst, _subroot, RIGHT, _subroot->right, data);
		else if(_pbst->dataCmp(data, _subroot->data)==-1)
			return removeHelp(_pbst, _subroot, LEFT, _subroot->left, data);
		else
		{
			struct Node *del = _subroot;
			if(_subroot->left==NULL)
			{
				if(ppNode==NULL)
					_pbst->root = _subroot->right;
				else
				{
					if(pivot==LEFT)
						ppNode->left = _subroot->right;
					else
						ppNode->right = _subroot->right;
				}
				_pbst->freeData(del->data);
				free(del);
			}
			else if(_subroot->right==NULL)
			{
				if(ppNode==NULL)
					_pbst->root = _subroot->left;
				else
				{
					if(pivot==LEFT)
						ppNode->left = _subroot->left;
					else
						ppNode->right = _subroot->left;

				}
				_pbst->freeData(del->data);
				free(del);
			}
			else
			{
				void *data = _pbst->allocData(del->data);
				removeMin(_pbst, _subroot, &data);
				_pbst->copyData(del->data, data);
				_pbst->freeData(data);
			}
			return true;
		}
	}
}

static struct Node* insertHelp(struct Bst *_pbst, struct Node **_psubroot, void *data)
{
	if(*_psubroot==NULL)
	{
		struct Node *node = (struct Node*)calloc(sizeof(struct Node), 1);
		if(node==NULL)
			return NULL;
		node->data = _pbst->allocData(data);
		if(node->data==NULL)
		{
			free(node);
			return NULL;
		}
		_pbst->copyData(node->data, data);
		(*_psubroot) = node;
		return node;
	}
	else if(_pbst->dataCmp(data, (*_psubroot)->data)>=0)
		return insertHelp(_pbst, &((*_psubroot)->right), data);
	else
		return insertHelp(_pbst, &((*_psubroot)->left), data);
}

static void delHelp(struct Bst *_pBst, struct Node *subroot)
{
	if(subroot==NULL)
		return;
	delHelp(_pBst, subroot->left);
	delHelp(_pBst, subroot->right);
	
	_pBst->freeData(subroot->data);
	free(subroot);
	return;

}

static BOOL removeMinHelp(struct Bst *_pbst, struct Node *subroot, void *data)
{
	if(subroot->left->left==NULL)
	{
		struct Node *min = subroot->left;
		_pbst->copyData(data, min->data);
		_pbst->freeData(min->data);

		subroot->left = min->right;

		free(min);
		return true;
	}
	else
		return removeMinHelp(_pbst, subroot->left, data);
}


void printHelp(struct Bst *_pbst, struct Node *_pNode, int level)
{
	if(_pNode==NULL)
		return;
	printHelp(_pbst, _pNode->left, level+1);
	int i;
	for(i=0;i<level;i++)
		printf(" ");
	_pbst->printData(_pNode->data);
	printf("\n");
	printHelp(_pbst, _pNode->right, level+1);
}

struct Bst* initBst(void *(*allocData)(void *),
			 int (*dataCmp)(void*, void*),
			 void (*freeData)(void *),
			 void (*copyData)(void *, void *),
			 void (*printData)(void *))
{
	struct Bst* _pbst = (struct Bst*)calloc(sizeof(struct Bst), 1);
	if(_pbst==NULL)
		return _pbst;
	
	_pbst->nodeCount = 0;
	_pbst->root = NULL;

	_pbst->allocData = allocData;
	_pbst->dataCmp = dataCmp;
	_pbst->freeData = freeData;
	_pbst->copyData = copyData;
	_pbst->printData = printData;
	return _pbst;
}

void print(struct Bst *_pbst)
{
	if(_pbst==NULL)
		return ;

	printHelp(_pbst, _pbst->root, 0);
}

void delBst(struct Bst *_pBst)
{
	if(_pBst==NULL)
		return;
	delHelp(_pBst, _pBst->root);
}

BOOL insert(struct Bst *_pBst, void *data)
{
	if(_pBst==NULL)
		return false;

	if(insertHelp(_pBst, &(_pBst->root), data)==NULL)
		return false;

	return true;
}

BOOL removeNode(struct Bst *_pBst, void *data)
{
	if(_pBst==NULL)
		return false;

	return removeHelp(_pBst, NULL, NONE, _pBst->root, data);
}

BOOL removeMin(struct Bst *_pBst, struct Node *root, void *data)
{
	if(root==NULL)
		return false;
	if(root->left==NULL)
	{
		struct Node *del = root;
		_pBst->copyData(data, del->data);
		_pBst->freeData(del->data);
		
		root = del->right;
		free(del);
		return true;
	}
	else
		return removeMinHelp(_pBst, root, data);
}

BOOL find(struct Bst *_pbst, void *data)
{
	if(_pbst==NULL||data==NULL)
		return false;
	return findHelp(_pbst, _pbst->root, data);
}
